package leetcode.D100.T20;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-08-09 14:47:58 星期一
 */

public class Solution {
    // 一刷
    /*public boolean isValid(String s) {
        if(s.length() % 2 > 0) {
            return false;
        }
        Deque<Character> dq = new LinkedList<>();
        for(int i=0; i<s.length(); ++i) {
            char c = s.charAt(i);
            if(c == '(' || c == '[' || c == '{') {
                dq.addFirst(c);
            } else {
                if(dq.isEmpty()) {
                    return false;
                }
                if((c == ')' && dq.getFirst() == '(') || (c == ']' && dq.getFirst() == '[') || (c == '}' && dq.getFirst() == '{')) {
                    dq.removeFirst();
                } else {
                    return false;
                }
            }
        }
        return dq.isEmpty();
    }*/

    // 二刷
    /*public boolean isValid(String s) {
        if(s.length() % 2 != 0)
            return false;
        Deque<Character> dq = new LinkedList<>();
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i++);
            if(dq.isEmpty()) {
                dq.addFirst(c);
                continue;
            }
            char d = dq.getFirst();
            if ((c == ')' && d == '(') ||
                    (c == ']' && d == '[') ||
                    (c == '}' && d == '{'))
                dq.removeFirst();
            else
                dq.addFirst(c);
        }
        return dq.isEmpty();
    }*/

    // 三刷
    /*public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (int i=0; i<s.length(); ++i) {
            char c = s.charAt(i);
            if (stack.isEmpty())
                stack.push(c);
            else if ((c == ')' && stack.peek() == '(')
                     || (c == ']' && stack.peek() == '[')
                      || (c == '}' && stack.peek() == '{'))
                stack.pop();
            else
                stack.push(c);
        }
        return stack.isEmpty();
    }*/

    // 四刷
    public boolean isValid(String s) {
        Deque<Character> dq = new LinkedList<>();
        for (int i=0; i<s.length(); ++i) {
            char c = s.charAt(i);
            if (dq.isEmpty())
                dq.push(c);
            else {
                if ((c == ')' && dq.peek() == '(') || (c == '}' && dq.peek() == '{') || (c == ']' && dq.peek() == '['))
                    dq.pop();
                else
                    dq.push(c);
            }
        }
        return dq.isEmpty();
    }
}
